The invention relates to programmable logic devices (PLDs). More particularly, the invention relates to methods of testing for shorts between interconnect lines in a partially defective PLD that will prevent the PLD from being used with a specified design.
Programmable logic devices (PLDs) are a well-known type of digital integrated circuit that can be programmed to perform specified logic functions. One type of PLD, the field programmable gate array (FPGA), typically includes an array of configurable logic blocks (CLBs) surrounded by a ring of programmable input/output blocks (IOBs). Some FPGAs also include additional logic blocks with special purposes (e.g., DLLs, RAM, and so forth).
The various logic blocks are interconnected by a programmable interconnect structure that includes a large number of programmable interconnect lines (e.g., metal wires). The interconnect lines and logic blocks are interconnected using programmable interconnect points (PIPs). A PIP can be, for example, a CMOS passgate. When the passgate is turned on (i.e., the PIP is enabled), the two interconnect lines on either side of the passgate are electrically connected. When the passgate is turned off (i.e., the PIP is disabled), the two interconnect lines are isolated from each other. Thus, by controlling the values on the gate terminals of the PIPs, circuit connections can be easily made and altered.
PIPs can be implemented in many different ways. For example, a buffered PIP can be implemented as a tristate buffer. When the tristate signal is low, the buffer output is not driven, and the two interconnect lines on either side of the buffer are isolated from each other. When the tristate signal is high, one of the interconnect lines drives the other interconnect line in a unidirectional connection.
Various exemplary types of PIPs are described by Freeman in U.S. Pat. No. Re. 34,363, by Carter in U.S. Pat. Nos. 4,695,740 and 4,713,557, by Hsieh in U.S. Pat. No. 4,835,418, and by Young in U.S. Pat. No. 5,517,135, all of which are hereby incorporated by reference. Some PIPs are unidirectional and some are bidirectional. Some are buffered and some are not buffered. However, the various types of PIPs typically have this in common, that they are controlled by a single data value stored in a memory cell called a configuration memory cell.
The logic blocks and PIPs in a PLD are typically programmed (configured) by loading data from a configuration data file into thousands of configuration memory cells that define how the logic blocks and interconnect lines are configured and interconnected. In Field Programmable Gate Arrays (FPGAs), for example, each configuration memory cell is implemented as a static RAM cell.
Each PLD typically contains many thousands of configuration memory cells. A fabrication defect in any one of these memory cells makes the PLD defective for most purposes, as by the very nature of an PLD a user design can be implemented using any of the programmable resources in the device. Hence, for example, an FPGA manufacturer typically tests the functionality of each logic block and each PIP in every FPGA prior to selling the FPGA to a customer.
One type of defect that can occur is a defect in a PIP or in the memory cell controlling the PIP, such that the PIP is always enabled. In this situation, the two nets on either side of the PIP are shorted together. A PLD having this type of defect is partially defective and cannot be sold as a fully functional device.
However, if a single, specified design (i.e., a given configuration data file) will be implemented in a PLD, it is not necessary for each and every PIP in the PLD to be fully functional. It is only necessary for each PIP that affects that particular design to be functional. Any PIP actually used in routing the design must either function properly, or the defect must be such that the PIP is permanently turned on. In addition, any PIP that, if defective, will undesirably short a net in the design to some other net in the design must either function properly, or the defect must be such that the PIP is permanently turned off.
These requirements can best be understood by reviewing an example that is now explained in connection with FIG. 1.
FIG. 1 shows a portion of a PLD that includes three logic blocks LB1-LB3, five interconnect lines IL0-IL4, and four PIPS P1-P4. Interconnect lines IL1-IL3 are coupled to logic blocks LB1-LB3, respectively. Interconnect lines IL1-IL3 can each be programmably coupled to interconnect line IL0 through PIPs P1-P3, respectively. Interconnect line IL4 can be programmably coupled to interconnect line IL3 through PIP P4.
PIPS P1-P4 are respectively controlled by four memory cells MC1-MC4. When the value stored in one of the memory cells is high, the passgate in the associated PIP is enabled. When the value stored in one of the memory cells is low, the interconnect lines on either side of the associated PIP are not connected together. They can be left unconnected or wired as parts of two separate circuits.
As an example, consider the case where memory cells MC1, MC2, and MC4 each store a high value and memory cell MC3 stores a low value. As specified by the configuration data file, PIPs P1 and P2 should be enabled, connecting together interconnect lines IL1, IL0, and IL2 to form a first net. PIP P4 should also be enabled, connecting together interconnect lines IL3 and IL4 to form a second net. PIP P3 should be disabled, isolating the first and second nets from each other.
Suppose that memory cell MC1 is defective, and the value stored in memory cell MC1 is permanently set to a high value. Because PIP P1 should be enabled for this design, there is no effect on the specified design. Therefore, this defect does not prevent this PLD from being used to implement the specified design. The effect is the same if there is some defect in the PIP itself that renders the PIP permanently enabled (i.e., turned on whenever the device is configured and/or power is supplied to the PLD).
However, suppose that memory cell MC1 or PIP P1 is defective such that PIP P1 is permanently disabled (i.e., turned off whenever the device is configured and/or power is supplied to the PLD). The first net is incomplete, so the specified design does not work in this partially defective PLD.
Now suppose that memory cell MC3 or PIP P3 is defective such that PIP P3 is permanently disabled. Because PIP P3 should be disabled for this design, there is no effect on the specified design. Therefore, this defect does not prevent this PLD from being used to implement the specified design.
However, suppose that memory cell MC3 or PIP P3 is defective such that PIP P1 is permanently enabled. The first and second nets are shorted together. The specified design does not work in this partially defective PLD.
PLDS are growing larger every year, and the larger an integrated circuit device, the more likely it is that the device will contain fabrication defects. Thus, larger PLDs are more expensive than smaller ones, not just because more silicon area is needed, but also because the likelihood of fabrication defects is higher. Thus, discarding all defective PLDs is an expensive alternative, and growing more expensive with time. However, the above examples clearly demonstrate that some partially defective PLDs can still be used in limited circumstances. A given partially defective PLD can be used with some specified designs, and not with other specified designs. Therefore, it is highly desirable to provide methods that contribute to the use of partially defective PLDs.
Clearly, if a partially defective PLD is to be used with a specified design, the PLD must be tested to see if the design will function properly in that device. One method of testing a design is simply to download the configuration data file for the design into the partially defective PLD and then operate the resulting circuit to see if it works. However, it can be a very lengthy process to test every conceivable combination of data values and data sequences that can occur in a complicated design. Therefore, it is generally preferred to perform a test of each PLD resource used in the specified design, and verify that the resource is operating correctly. If each PLD resource affecting the design functions properly and the customer has generated and tested the design correctly, it can be assumed that the PLD can be used for that design.
One test that is typically performed to determine the suitability of a PLD for a specified design is a xe2x80x9cshort testxe2x80x9d (i.e., a test for inadvertent couplings between two nodes). In this test, all nets that are used in the design are driven to a known value. At the same time, all routing resources not used in the design are driven to the opposite value. Logic blocks driven by the nets are configured to check for the expected value on each net.
For example, all nets used in the design can be driven high by configuring the logic block driving each net to provide a high value, while all unused PLD routing resources are tied to ground. Additionally or alternatively, all nets used in the design can be driven low by configuring the logic block driving each net to provide a low value, while all unused PLD routing resources are tied to power high.
The value on each net, or the result of a logical function performed on one or more of the nets, is typically provided to the tester via an output terminal of the PLD. For example, the value or result can be read back from the PLD using well-known PLD data readback or JTAG techniques. The logic value is then compared with the expected value. If the observed value does not match the expected value, one or more nets are shorted to unused interconnect resources. The tested PLD cannot be used for the specified design.
These known short tests can detect a defectively enabled PIP between a net used in the specified design and an unused interconnect resource. However, shorting together two nets that are both tied to the same value does not give an anomalous result. Hence, the known test methods do not detect a defectively enabled PIP between two different nets when both nets are used in the specified design.
Therefore, it is desirable to provide methods of detecting shorts between two nets of a specified design in a partially defective PLD.
The invention provides methods of detecting shorts affecting nets of a specified design in a partially defective programmable logic device (PLD).
According to the methods of the invention, the nets participating in the specified design are identified, and the interconnect lines used to implement each net are identified. The nets are then divided into two or more groups, where no two nets in a single group can be shorted together by the inadvertent enablement of a single programmable interconnect point (PIP) between two interconnect lines. In other words, if two interconnect lines used to implement two different nets are separated by a single PIP, the nets are assigned to different groups.
In one embodiment, the nets are divided into groups by identifying potentially conflicting pairs of interconnect lines (pairs of interconnect lines that can be shorted together by the inadvertent enablement of a single PIP). Potentially conflicting pairs of nets are identified by their association with the potentially conflicting pairs of interconnect lines. All of the nets in the specified design are then divided into groups, such that no two of the nets in a single group form a potentially conflicting pair of nets.
In one embodiment, the nets are divided into groups using the well-known graph coloring algorithm. The nodes in the graph are the nets that are used in the specified design. The arcs in the graph (i.e., the adjacencies) are the potential conflicts between two nets that can potentially be shorted together by a single defectively-enabled PIP.
Once all of the nets in the specified design have been divided into groups, the groups are tested for inadvertent shorts.
According to a first aspect of the invention, each group is tested sequentially, i.e., one group is tested at a time. For example, all nets in a first group are tested first, followed by all nets in the second group, and so forth.
In one embodiment, each group of nets is tested by applying a first value to each net in the group and applying a second and different value to all interconnect lines not associated with nets in the group. The values of the nets in the group under test are then monitored and compared to the first value to determine whether any net in the group is shorted to an interconnect line not associated with any net in the group. This embodiment detects all single defects (e.g., defects to a single PIP or to a memory cell controlling a single PIP) that affect the design by shorting together two nets in the design. In addition, this embodiment detects all single defects that affect the design by shorting a net in the design to an unused interconnect line.
In another embodiment, each group of nets is tested by applying a first value to each net in the group and applying a second and different value to all nets in other groups. The values of the nets in the group under test are then monitored and compared to the first value to determine whether any net in the group is shorted to a net in another group. This embodiment detects all single defects that affect the design by shorting together two nets in the design. Single defects that affect the design by shorting a net in the design to an unused interconnect line are not detected using this method.
According to the first aspect of the invention, the nets are divided into groups and each group is tested sequentially. However, a second aspect of the invention allows for the simultaneous testing of nets in all groups.
According to a second aspect of the invention, all of the groups are tested at the same time. However, each group of nets is tested using a different applied stimulus pattern, i.e., a different sequence of high and low values. Therefore, no two nets that can be shorted together by the inadvertent enablement of a single PIP use the same stimulus pattern. Hence, any single defect that shorts together two nets will be detected by comparing the detected value pattern for a net to the stimulus pattern applied to the group of nets.
In some embodiments, the detected value pattern and the stimulus patterns applied to other groups of nets are compared. From the results of this comparison, it can be determined which two groups of nets are participating in the short.